#include <stdio.h>
#include <stdlib.h>/*该文件包含exit()等函数*/
#include <malloc.h>/*该文件包含malloc()等函数*/
#define STACK_MAX_SIZE 100 // 栈最多支持存放100个数据元素
#define bool int

typedef struct stack {
    int * base;
    int * top;
    int number_of_elements; // 栈内实际数据元素个数
} * Stack;

// 初始化名为s的栈，初始化成功，返回0，否则返回1。
int init_stack(Stack* s){
    int *num;
    num = (int *) malloc(STACK_MAX_SIZE * sizeof (int ));
    (*s) = malloc(sizeof  (struct stack));
    (*s)->base = num;
    (*s)->top = (*s)->base;
    (*s)->number_of_elements = STACK_MAX_SIZE;
    return 0;
}

// 入栈。返回值表示是否压栈成功：0，成功；1，不成功。
int push(Stack s, char operator_or_operand){

    if(s->top - s->base == s-> number_of_elements) {
        printf("Stack full");
        return 1;
    }
    *s->top= operator_or_operand ;
    s->top++;

    return 0;
}

// 出栈。返回值表示是否出栈成功：0，成功，1，不成功。
int pop(Stack s, char * p_operator_or_operand){

    if (s-> top == s->base ){
        printf("Stack is empty 1 \n");
        return 1;
    }

    *p_operator_or_operand = *(s->top - 1);
    s->top -- ;

    return 0;
}

//// 只返回栈顶元素，通过result变量返回栈顶元素的值。函数返回值用于表示执行状态：0，成功；1，不成功。
int get_top(Stack s, char * symbol){
    if (s->top != s->base ) {
        * symbol = *(s->top-1);
        return 0;
    }
    return 1;
}

// 判断刚扫描到的symbol是否操作符。如果symbol是操作符，返回1，否则返回0。
bool is_operator(char symbol){
    switch (symbol) {
        case '+' :
        case '-' :
        case '*' :
        case '/' :
        case '#' :
        case '(' :
        case ')' : return 1 ;
        default : return 0 ;
    }

}

// 判断刚扫描到的symbol是否操作数。如果symbol是操作数，返回1，否则返回0。
bool is_operand(char symbol) {
    if (symbol <= 57 && symbol >= 48)
        return 1;
    else
        return 0;
}


int compare(char operator_on_stack_top,char just_scanned_operator){//比较操作符
    int i, j;
    char youxianji[][7] = {
            /*运算符之间的优先级制作成一张表格*/
            {'>', '>', '<', '<', '<', '>', '>'},
            {'>', '>', '<', '<', '<', '>', '>'},
            {'>', '>', '>', '>', '<', '>', '>'},
            {'>', '>', '>', '>', '<', '>', '>'},
            {'<', '<', '<', '<', '<', '=', '0'},
            {'>', '>', '>', '>', '0', '>', '>'},
            {'<', '<', '<', '<', '<', '0', '='}
    };
    switch(operator_on_stack_top){
        case '+': i=0; break;
        case '-': i=1; break;
        case '*': i=2; break;
        case '/': i=3; break;
        case '(': i=4; break;
        case ')': i=5; break;
        case '#': i=6; break;
    }
    switch (just_scanned_operator) {
        case '+':j = 0;break;
        case '-':j = 1;break;
        case '*':j = 2;break;
        case '/':j = 3;break;
        case '(':j = 4;break;
        case ')':j = 5;break;
        case '#':j = 6;break;
    }
    switch (youxianji[i][j]) {
        case '>':
            return 1;
        case '<':
            return -1;
        case '=':
            return 0;
        case '0':
            return 5;
    }


}
int compute(char right,char left,char operator,int *result){//计算操作数
    int i;
    int j;
    switch (left) {
        case '0':i=0;break;
        case '1':i=1;break;
        case '2':i=2;break;
        case '3':i=3;break;
        case '4':i=4;break;
        case '5':i=5;break;
        case '6':i=6;break;
        case '7':i=7;break;
        case '8':i=8;break;
        case '9':i=9;break;
        default:printf("输入错误1\n");
    }
    switch (right) {
        case '0':j=0;break;
        case '1':j=1;break;
        case '2':j=2;break;
        case '3':j=3;break;
        case '4':j=4;break;
        case '5':j=5;break;
        case '6':j=6;break;
        case '7':j=7;break;
        case '8':j=8;break;
        case '9':j=9;break;
        default:
            printf("输入错误2\n");break;
    }
    switch (operator) {
        case '+':*result=i+j;break;
        case '-':*result=i-j;break;
        case '*':*result=i*j;break;
        case '/':*result=i/j;break;
    }
//    printf("I=%d\nJ=%d\n",i,j);
//    printf("Operator:%c\n",operator);
    return 1;
}


int evaluate(char * expression, int * result){
    Stack OPND;//操作数或运算结果
    Stack OPTR;//运算符
    int ex_point=0;
    int isFlag=0;
    int out;
    int count=1;
    char end_element;
    char change;
    char is_exit='0';
    char operator;
    char top_element;
    char pop_element_i;
    char pop_element_j;
    char pop_element_throw;
    init_stack(&OPND);
    init_stack(&OPTR);

    if(is_operator(expression[ex_point]))
        push(OPTR,expression[ex_point]);
//    printf("push #\n");
    ex_point++;
    for (;;) {
//        printf("------Loading_%d-------\n",count);
        count++;
        if(is_operand(expression[ex_point])){
            push(OPND,expression[ex_point]);
//            printf("push and \n");
            ex_point++;

        }
        if(is_operator(expression[ex_point])){
            get_top(OPTR,&top_element);
            switch (compare(top_element,expression[ex_point])) {

                case 1:
//                    printf("case1\n");
                    pop(OPND,&pop_element_i);
                    pop(OPND,&pop_element_j);
                    pop(OPTR,&operator);
                    compute(pop_element_i,pop_element_j,operator,&out);
                    change=out+48;
//                    printf("value:%d\n",out);
                    push(OPND,change);
                    if (expression[ex_point]!='#'){
                        get_top(OPTR,&top_element);
                        if (compare(top_element,expression[ex_point])==0){
//                            printf("匹配括号\n");
                            pop(OPTR,&pop_element_throw);
                        }else
                            push(OPTR,expression[ex_point]);
                    }
                    isFlag=0;
                    break;
                case 0:
                    pop(OPTR,&pop_element_throw);
//                    printf("case0\n");

                    is_exit=expression[ex_point];
                    isFlag=1;
                    break;
                case -1:
                    push(OPTR,expression[ex_point]);
//                    printf("case-1\n");
                    isFlag=0;
                    break;
                case 5:
//                    printf("default");
                    break;
            }
            is_exit=expression[ex_point];
            if(is_exit=='#'&&isFlag==1){
//                printf("匹配井号\n返回结果\n\n");
                break;
            }
            if(expression[ex_point]!='#')
                ex_point++;

        }


    }
    get_top(OPND,&end_element);
    //return 1;
    *result=end_element-48;

    return 0;


}
int main(int argc, char * argv[]) {
    char * exp5 = "#(1+((1+1)*3/2))-2#";
    char * exp3 = "#1+(1+1)*3/2-2#";
    int result;
    evaluate(exp5, &result);
    printf("result = %d \n",result);
    evaluate(exp3, &result);
    printf("result = %d \n",result);
    return 0;
}
